package com.peng.leetcode.other;

/**
 * Trap
 * <p>
 * 面试题 17.21. 直方图的水量
 *
 * @author: lupeng6
 * @create: 2021/4/2 14:39
 */
public class Trap {

    public static void main(String[] args) {
        int[] height = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
        System.out.println(new Trap().trap(height));
    }

    public int trap(int[] height) {
        int len = height.length;

        int[] leftMax = new int[len];
        int[] rightMax = new int[len];
        leftMax[0] = height[0];
        rightMax[len - 1] = height[len - 1];

        for (int i = 1; i < len; i++) {
            leftMax[i] = Math.max(leftMax[i - 1], height[i]);
        }

        for (int j = len - 2; j >= 0; j--) {
            rightMax[j] = Math.max(rightMax[j + 1], height[j]);
        }

        int answer = 0;

        for (int i = 0; i < len; i++) {
            answer += Math.min(leftMax[i], rightMax[i]) - height[i];
        }

        return answer;
    }
}
